package main

import "fmt"

/*
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中
的开始位置和结束位置。
如果数组中不存在目标值 target，返回[-1, -1]。
你必须设计并实现时间复杂度为O(log n)的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
*/

//双指针
func searchRange1(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	l, r := 0, len(nums)-1
	var res []int
	for nums[l] < target && l < r {
		l++
	}
	for nums[r] > target && l < r {
		r--
	}
	if l <= r && nums[l] == target {
		res = append(res, l, r)
		return res
	}
	return []int{-1, -1}
}

//二分法
func searchRange2(nums []int, target int) []int {
	var l, r = 0, len(nums) - 1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] >= target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	if l == len(nums) || nums[l] != target {
		//如果l==len(nums) ->
		return []int{-1, -1}
	}
	var cnt = 0
	for i := l + 1; i < len(nums); i++ {
		if nums[i] == target {
			cnt++
		}
	}
	return []int{l, l + cnt}
}

func main() {
	num := []int{5, 7, 7, 8, 8}
	fmt.Println(searchRange2(num, 6))
}
